Image pyramids are used by many types of image-processing applications. An image pyramid is a representation of an image at different resolutions, where the same downsampling filter is used to go from a finer image to a coarser image within the pyramid. One popular type of image pyramid is a mipmap pyramid. The mipmap pyramid is a hierarchy of filtered versions of an original image, such that successive levels correspond to filtered frequencies. In other words, the mipmap pyramid decomposes an image into a series of filtered images. A filter is applied to a finer level, and then that level is subsampled to form the next coarser level. When stacked one on top of another this series of filtered images forms a pyramid structure.
The mipmap pyramid can use a variety of filters, including a box filter and a Gaussian filter. A Gaussian pyramid is a special case of the mipmap pyramid, and occurs when using a Gaussian filter. Usually, better-quality pyramids are obtained when using a more complex filter, such as a Gaussian filter, which uses a broader set of samples than the box filter.
FIG. 1 illustrates a mipmap pyramid 100 having four levels, namely, Level 0, Level 1, Level 2, and Level 3. Level 3 represents a sample image at the finest resolution level, which is also called an original image or given image. Pixels at Level 3 are downsampled to produce pixels at Level 2, where Level 2 has fewer pixels than Level 3. This is repeated for successively higher levels in the pyramid 100 until a single pixel remains (Level 0 in FIG. 1), which is the original image blurred to a single pixel.
By way of example, the fine-scale original image at Level 3 in FIG. 1 has a size of 8×8 (or 82). To obtain Level 2, the pixels of Level 3 are downsampled by a factor of 2. As shown in FIG. 1, this means that the number of pixels in Level 2 is 42. For example, if the downsampling filter is a box filter, the downsampling operation from Level 3 to Level 2 involves taking 4 Level 3 pixels 110 and averaging these pixels to obtain a single pixel 120 in Level 2. As stated above, if a more complex filter such as a Gaussian filter is used, a broader set of samples is required. Increasingly coarser levels are obtained by repeating this downsampling such that, for example, Level 1 contains 22 pixels and Level 0 contains a single pixel (12). As stated above, this pixel represents the original image blurred to a single pixel.
A pixel at a coarse level, therefore, contains the result of applying the filter to a larger number of pixels at the finest level. For example, the four pixels of the second coarsest level of a mipmap pyramid contain the result of the filter applied to each four quadrants of the initial image. Each successively coarser level corresponds to applying the filter to a larger window of the finest level.
FIG. 2 illustrates an example in one-dimension (1-D) of the downsampling of the mipmap pyramid 100 shown in FIG. 1. In FIG. 2, an example of filtering using a box filter is shown in order to simplify the figure. In the box filtering example shown in FIG. 2, in order to produce a pixel 210 in Level 2, pixel 220 and pixel 230 in Level 3 are used. Similarly, to produce a pixel 240 in Level 1, pixel 210 and pixel 250 in Level 2 are used. And, to produce the coarsest level pixel 260 in Level 0, pixel 240 and pixel 270 in Level 1 are used.
One drawback of the mipmap pyramid is that a coarser level only contains the result of the filter applied at quantized locations within the finest resolution image. The second coarsest level will contain information for the filter applied to the four quadrants, but it is not possible to obtain information for a filter of a same size (a quarter of the image) applied to any other locations. Depending on the application, this can lead to artifacts. In particular, with multi-resolution texture synthesis, significant features tend to appear at quantized locations. This is called spatial quantization.
FIG. 3 illustrates an example of this spatial quantization that occurs when using a mipmap pyramid in a texture synthesis application. A synthesized texture 300 is formed using an exemplar 310 having a size of 642 pixels. It should be noted that in the context of texture synthesis, an original image is referred to as an exemplar. In this case, the mipmap pyramid has six levels (Levels 0 to 6). A significant feature of the exemplar 310 is a red dot 320. It can be seen that the red dot 320 appears in the synthesized texture 300 multiple times but only at quantized spatial locations. This is due to the spatial quantization resulting from the mipmap pyramid.
One current texture synthesis algorithm introduces a quadtree pyramid for uses in texture synthesis instead of a mipmap pyramid. The quadtree pyramid is a data structure for hierarchical search of image data. With the quadtree pyramid, an image is divided into four quadrants or nodes, with each of the nodes having four children nodes. The quadtree pyramid uses an array of multiple smaller images at each level in the quadtree pyramid rather than a single image at each level. Because the quadtree samples are not spatially continuous, however, neighboring relationships between pixels are non-continuous and there are quantized jumps between multiple images. This makes pixel addressing difficult and complex.